#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include "galois.h"
#include "galois_add.h"

main (int argc, char **argv)
{
	int remainder[2][5], r1[5];
	int quotient[5];

	int w;
	int i;
	int w32;
	int a;
	int high_bit;
	int high_bit_r;
	int inv;
	int shift_count;
	int s, t;
	int mask0;
	int a1, a0, tmp;

	if (argc != 3) { fprintf(stderr, "usage: prog w a\n"); exit(1); }

	w = atoi(argv[1]);
	a = atoi(argv[2]);
	mask0 = (1 << (w/4)) -1;
	if (w > 32) exit(1);
	if (w == 32) w32 = 1; else w32 = 0;

	s = 3;
	t = 8;

	remainder[0][0] = t;
	remainder[0][1] = s;
	remainder[0][2] = 1;
	remainder[0][3] = 0;
	remainder[0][4] = 1;

	remainder[1][0] = a & mask0;
	remainder[1][1] = (a >> (w/4)) & mask0;
	remainder[1][2] = (a >> (2*(w/4))) & mask0;
	remainder[1][3] = (a >> (3*(w/4))) & mask0;
	remainder[1][4] = 0;

	a1 = 1; a0 = 0;

	high_bit = 4;
	high_bit_r = 4;
	while (high_bit > 0) {
		for (i = 0; i < 5; i++) quotient[i] = 0;
		high_bit = high_bit_r;

		for (high_bit_r = 4; remainder[1][high_bit_r] == 0; high_bit_r--);

		/* This is the polynomial division part */
		while(high_bit >= high_bit_r) {
			for (i = 0; i < 5; i++) r1[i] = remainder[1][i];
			shift_count = 0;

			/* If w == 32, the width is bigger than an int, so deal with that: */
/*
			if (w32) {
				while((r1 & (1 << (high_bit-1))) == 0) { r1 <<= 1; shift_count++; }
				r1 <<= 1; shift_count++;
				w32 = 0;
			} else while((r1 & (1 << high_bit)) == 0) { r1 <<= 1; shift_count++; }
*/
			shift_count = high_bit - high_bit_r;
			inv = galois_single_divide(remainder[0][high_bit], r1[high_bit_r], (w/4));
			for (i = 0; i < 5; i++) r1[i] = galois_single_multiply(inv, r1[i], (w/4));

			/* set the quotient */
			quotient[shift_count] = inv;

			/* next remainder in the division process */
			for (i = 0; i <= high_bit_r; i++) remainder[0][i+shift_count] ^= r1[i];
			while(remainder[0][high_bit] == 0) high_bit--;
		}

		memcpy(r1, remainder[0], sizeof(int) * 5);
		memcpy(remainder[0], remainder[1], sizeof(int) * 5);
		memcpy(remainder[1], r1, sizeof(int) * 5);
		tmp = 0;
		for (i = 3; i >= 0; i--) { tmp <<= (w/4); tmp ^= quotient[i]; }
		a1 = galois_composite_multiply_k4(tmp, a1, w);
		a1 ^= a0;
		a0 = a1;
	}
	if (remainder[1][0] != 1) {
		for (i = 0; i < 4; i++) {
			r1[i] = galois_single_multiply(remainder[1][0], (a1 >> (i * (w/4)) & mask0), (w/4));
		}
		a1 = 0;
		for (i = 3; i >= 0; i--) { a1 <<= (w/4); a1 ^= r1[i]; }
	}
	printf("%d\n", a1);
}
